#include <bits/stdc++.h>

using namespace std;

const int maxn=100005;
const double eps=1e-5;
int seq[maxn];
int seg[4*maxn];
int lst[maxn],ans[maxn];
vector<int> dvi[maxn],pre[maxn];
struct Q{ int l,r,id;};
Q qry[maxn];

bool cmpByL(const Q &x,const Q &y){return x.l<y.l;}
bool cmpByR(const Q &x,const Q &y){return x.r<y.r;}

int dest,val,bg,ed;
void ins(int p,int l,int r){
    while(l<r){
        seg[p]=max(seg[p],val);
        int mid=(l+r)>>1;
        if(dest<=mid){
            p<<=1;
            r=mid;
        }else{
            p<<=1;
            p|=1;
            l=mid+1;
        }
    }
    seg[p]=max(seg[p],val);
}
int query(int p,int l,int r){
    if(bg<=l&&ed>=r) return seg[p];
    int mid=(l+r)>>1;
    if(ed<=mid) return query(p<<1,l,mid);
    else if(bg>mid) return query((p<<1)|1,mid+1,r);
    else return max(query(p<<1,l,mid),query((p<<1)|1,mid+1,r));
}

int main(){
     int n,m,last;

     scanf("%d",&n);
     for(int i=1;i<=n;i++) scanf("%d",seq+i);
     scanf("%d",&m);
     for(int i=1;i<=m;i++){
        scanf("%d%d",&qry[i].l,&qry[i].r);
        qry[i].id=i;
     }

     for(int i=n;i>0;i--){
        for(int j=1,_end_=floor(sqrt(seq[i])+eps);j<=_end_;j++){
            if(seq[i]%j) continue;
            dvi[i].push_back(j);
            pre[i].push_back(lst[j]);
            lst[j]=i;
            int k=seq[i]/j;
            if(k!=j){
                dvi[i].push_back(k);
                pre[i].push_back(lst[k]);
                lst[k]=i;
            }
        }
     }
     sort(qry+1,qry+1+m,cmpByL);
     last=1;
     for(int i=1;i<=m;i++){
        for(;last<qry[i].l;last++){
            for(int j=0;j<dvi[last].size();j++){
                dest=pre[last][j];
                val=dvi[last][j];
                if(dest) ins(1,1,n);
            }
        }
        bg=qry[i].l;
        ed=qry[i].r;
        ans[qry[i].id]=query(1,1,n);
     }

     memset(lst,0,sizeof(lst));
     memset(seg,0,sizeof(seg));
     for(int i=1;i<=n;i++){
        for(int j=0;j<dvi[i].size();j++){
            const int &dv=dvi[i][j];
            pre[i][j]=lst[dv];
            lst[dv]=i;
        }
     }
     last=n;
     sort(qry+1,qry+1+m,cmpByR);
     for(int i=m;i>=1;i--){
        for(;last>qry[i].r;last--){
            for(int j=0;j<dvi[last].size();j++){
                dest=pre[last][j];
                val=dvi[last][j];
                if(dest) ins(1,1,n);
            }
        }
        bg=qry[i].l;
        ed=qry[i].r;
        ans[qry[i].id]=max(ans[qry[i].id],query(1,1,n));
     }

     for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
}
